/**
 * 
 */
package process.models;

import java.util.Random;
import java.util.Vector;

import data.Distance;
import data.SimilaritySet;

/**
 * The algorithm of K-means.
 * @author yexijiang
 * @date Jul 15, 2008
 */
public class KMeans extends Clusterer
{

	private int m_Dimension;
	private int m_NumberOfClusters;
	private int m_Sequence[];
	
	private SimilaritySet m_Set;
	private Vector<String> m_SetLabels;
	private Vector<Double> m_ClusterCenters[];
	private Vector<String> m_TagCluster[];
	private Distance m_DistFunc;
	
	
	public KMeans(int sequence[], int numOfCluster, SimilaritySet set, Vector<String> labels, Distance func)
	{
		m_Sequence = sequence;
		m_Dimension = sequence.length;
		m_NumberOfClusters = numOfCluster;
		m_Set = set;
		m_SetLabels = labels;
		m_DistFunc = func;
		
		m_ClusterCenters = new Vector[m_NumberOfClusters];
		
		for(int i = 0; i < m_ClusterCenters.length; ++i)
		{
			m_ClusterCenters[i] = new Vector<Double>();
		}
		
	}
	
	public Vector<String>[] doClustering()
	{
		
		//	initialize the center to the first several record
		
		Random r= new Random();
		int randomIndex = Math.abs(r.nextInt()) % (m_SetLabels.size() - m_NumberOfClusters);
		
		for(int i = 0; i < m_NumberOfClusters; ++i)
		{
			m_ClusterCenters[i] = m_Set.getRecordByKeys(m_SetLabels.get(randomIndex + i));

		}
		
		//	re-cluster until the clusters remain the same

		int loop = 0;
		do{
			Vector<String> clusters[] = new Vector[m_NumberOfClusters];
			for(int i = 0; i < clusters.length; ++i)
			{
				clusters[i] = new Vector<String>();
			}
			
			for(int i = 0; i < clusters.length; ++i)
			{
				clusters[i].clear();
			}
			
			//	put the label into cluster
			for(int i = 0; i < m_Set.size(); ++i)	//	for each record
			{
				int clusterId = 0;
				String label = m_SetLabels.get(i);
				Vector<Double> vec = m_Set.getRecordByKeys(label);
				double dist = m_DistFunc.distance(vec, m_ClusterCenters[0]);
				for(int j = 0; j < m_ClusterCenters.length; ++j)	//	loop the vectors in the set
				{
					double tmpDist = m_DistFunc.distance(vec, m_ClusterCenters[j]);
					if(dist > tmpDist)
					{
						dist = tmpDist;
						clusterId = j;
					}
				}
				clusters[clusterId].add(label);
			}
			
			//	re-calculate the center
			for(int i = 0; i < m_ClusterCenters.length; ++i)	//	for each clusters' center
			{
				for(int j = 0; j < m_ClusterCenters[i].size(); ++j)	//	for each dimension of the center
				{
					double value = 0.0;
					for(int k = 0; k < clusters[i].size(); ++k)	//	for each element in the cluster
					{
						String label = clusters[i].get(k);
						value += m_Set.getRecordByKeys(label).get(j);
					}
					value /= clusters[i].size();
					m_ClusterCenters[i].set(j, value);	//	set the j-th dimension to the new center
				}
			}
			
			++loop;
			
			if(loop > 1)
			{
				if(false == clusterChange(clusters))	//	if the clusters remain the same, stop
					break;
			}
			
			m_TagCluster = clusters;
			
		}while(true);
		
		//	compare to all 1 vector
		Vector<Double> vO = new Vector<Double>();
		for(int i = 0; i < m_Dimension; ++i)
		{
			vO.add(1.0);
		} 
		
		//	compare all clusters' center to target tag to get the distance
		double dist[] = new double[m_ClusterCenters.length];
		for(int i = 0; i < m_ClusterCenters.length; ++i)
		{
			dist[i] = m_DistFunc.distance(vO, m_ClusterCenters[i]);
			//System.out.println(dist[i]);
		}
		
		//	bubble sort
		String tmp;
		for(int i = 0; i < m_TagCluster.length - 1; ++i)
		{
			for(int j = m_TagCluster.length - 1; j > 0 ; --j)
			{
				if(dist[j - 1] > dist[j])
				{
					double t = dist[j - 1];
					dist[j - 1] = dist[j];
					dist[j] = t;
					Vector<String> tmpV = m_TagCluster[j - 1];
					m_TagCluster[j - 1] = m_TagCluster[j];
					m_TagCluster[j] = tmpV;
					
					Vector<Double> tmpC = m_ClusterCenters[j - 1];
					m_ClusterCenters[j - 1] = m_ClusterCenters[j];
					m_ClusterCenters[j] = tmpC;
				}
			}
		}
		
		//System.out.println("After sort.");
		for(int i = 0; i < m_ClusterCenters.length; ++i)
		{
			dist[i] = m_DistFunc.distance(vO, m_ClusterCenters[i]);
			//System.out.println(dist[i]);
		}
		
		return m_TagCluster;
	}
	
	//	test whether the clusters are changed
	private boolean clusterChange(Vector<String> vsNew[])
	{
		
		for(int i = 0; i < m_TagCluster.length; ++i)	//	compare each cluster
		{
			if(false == clusterEqual(m_TagCluster[i], vsNew[i]))
			{
				return true;
			}
		}
		
		return false;
	}
	
	//	test whether two clusters equals
	private boolean clusterEqual(Vector<String> vLast, Vector<String> vNew)
	{
		if(vLast.size() != vNew.size())
			return false;
		
		for(int i = 0; i < vLast.size(); ++i)
		{
			if(false == vLast.get(i).equals(vNew.get(i)))
				return false;
		}
		
		return true;
	}
	
	public int getClusterNumber()
	{
		return m_NumberOfClusters;
	}
	
}
